package ShortestPath;

import java.util.*;

public class WordLadder {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 每次变化的字符都必须是 wordList 里面的字符
        Set<Character> existChar = new HashSet<>();
        for(String s : wordList) {
            char[] tmp = s.toCharArray();
            for(char c : tmp) {
                existChar.add(c);
            }
        }
        // 用数组来保存 existChar 里面的字符, 方便后续修改
        char[] change = new char[existChar.size()];
        int index = 0;
        for(Character c : existChar) {
            change[index++] = c;
        }

        Set<String> visit = new HashSet<>(); // 记录已经访问过的序列
        Set<String> hash = new HashSet<>(); // 记录字典中的单词
        for(String s : wordList) {
            hash.add(s);
        }

        if(beginWord.equals(endWord)) {
            // 初始序列和最终序列相同
            return 0;
        }
        if(!hash.contains(endWord)) {
            // 如果字典中不存在最终序列, 返回
            return 0;
        }

        // 用队列存储满足条件的节点
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        visit.add(beginWord);

        // 记录走的步伐数
        int step = 0;
        while(!queue.isEmpty()) {
            // 进入这里, 说明要往外走一层, 即沿着各条路向前走一步
            step++;

            int size = queue.size(); // 记录每层节点数
            while(size-- != 0) {
                // 取出点
                String point = queue.poll();

                // 遍历下一层节点
                for(int i = 0; i < beginWord.length(); i++) {
                    // 每次只能修改原序列其中一个字符
                    char[] tmp = point.toCharArray();
                    for(int j = 0; j < change.length; j++) {
                        tmp[i] = change[j];
                        String nextNode = new String(tmp);
                        if(hash.contains(nextNode) && !visit.contains(nextNode)) {
                            // 如果字典中存在修改后的序列 并且 该序列并没有被访问过, 可以添加到队列中
                            if(nextNode.equals(endWord)) {
                                // 如果修改后的序列与 end 序列相同, 说明找到最短路径了
                                return step + 1;
                            }
                            queue.offer(nextNode);
                            visit.add(nextNode);
                        }
                    }
                }
            }
        }
        return 0;
    }
}
